import java.util.LinkedList;
import java.util.List;

/**
 * \* Created with IntelliJ IDEA.
 * \* User: 冯若航
 * \* Date: 2021/6/15
 * \* Time: 22:51
 * \* To change this template use File | Settings | File Templates.
 * \* Description:
 * \
 */
public class 全排列 {
    /**存储结果*/
    List<List<Integer>> res=new LinkedList<>();

    /**
     * 主函数
     * @param nums
     * @return
     */
    public List<List<Integer>> permute(int[] nums) {
        LinkedList<Integer> track=new LinkedList<>();
        backtrack(nums,track);
        return res;
    }

    /**
     *结束条件：nums 中的元素全都在 track 中出现
     * @param nums 结束条件：nums 中的元素全都在 track 中出现
     * @param track 记录在 track 中
     */
    void backtrack(int[] nums,LinkedList<Integer> track){
        //结束条件
        if(track.size()==nums.length){
            res.add(new LinkedList<Integer>(track));
            return;
        }
        //开始做选择
        for(int i=0;i<nums.length;i++){
            //排除不合法的选择
            if(track.contains(nums[i])){
                continue;
            }
            //做选择
            track.add(nums[i]);
            //进入下一层
            backtrack(nums,track);
            //撤销选择
            track.removeLast();
        }
    }
}